package sf.tree;

public class BinarySearchTree implements Tree{

    private static class Node {
        int key;
        int value;
        Node left; // 左子树
        Node right;// 右子树
    }

    private Node root = null;

    @Override
    public void add(int key, int value) {
        final Node insert = insert(root, key, value);
        if (root == null) {
            root = insert;
        }
    }

    private static Node insert(Node node,int key, int value) {
        // insert的时候添加东西，然后
        if (node == null) {
            Node returnNode = new Node();
            returnNode.key = key;
            returnNode.value = value;
            return returnNode;
        } else {
            if (key < node.key) {
                // 左子树中插入
                node.left = insert(node.left, key, value);

            } else if (key == node.key) {
                // 替换
                node.value = value;
            } else {
                node.right = insert(node.right, key, value);
            }
            return node;
        }
    }

    @Override
    public Integer get(int key) {
        return null;
    }

    @Override
    public boolean contain(int key) {// 查找
        return false;
    }

    private static Node find(Node node,int key) {
        if (node == null) {
            return null;
        }
        if (node.key == key) {
            return node;
        }
        if (key < node.key) {
            // 往左找
            return find(node.left, key);
        } else {
            return find(node.right, key);
        }
    }

    @Override
    public Integer remove(int key) {
        return null;
    }
}
